class Solution {
public:
    int countDigitOne(int n) {
        // mulk 表示 10^k
        // 在下面的代码中，可以发现 k 并没有被直接使用到（都是使用 10^k）
        // 但为了让代码看起来更加直观，这里保留了 k
        long long mulk = 1;
        int ans = 0;
        while(mulk <= n){
            ans += (n / (mulk * 10)) * mulk + max(min(n % (mulk * 10) - mulk + 1, mulk), 0LL);
            mulk *= 10;
        }
        return ans;
    }
};


/**
 * 2021.8.16补大前天
 * 分别计算各个位上 1 出现的次数然后相加
 * 对于百位上的 1：
 *      -每一千个数都会出现 100 次（100~199） 这部分 = n / 1000 * 100
 *      -不足一千的那部分分三种情况讨论：
 *           -如果小于 100: 不会在百位上出现 1
 *           -如果在区间[100,199]中，则为 n % 1000 - 100 + 1 个 1
 *           -如果大于 199，那么有 100 个 1
 *      -这部分可以用一个式子来表示：max(min((n % 1000) - 100 + 1, 100), 0LL)
 */
